package com.ting.test.algorithms.二叉树;


import java.util.ArrayList;
import java.util.List;

public class N叉树转二叉树 {
    public static void main(String[] args) {
        n2bin(new NTreeNode(3));///n叉树 转二叉树
        bin2n(new TreeNode(3));///二叉树转n叉树
    }

    private static NTreeNode bin2n(TreeNode treeNode) {
        if (null == treeNode) {
            return null;
        }
        NTreeNode node = new NTreeNode(treeNode.val);
        node.childrens = de(treeNode.left);
        return node;
    }

    /**
     * 将二叉树转为n叉树
     *
     * @param head
     * @return
     */
    private static List<NTreeNode> de(TreeNode head) {
        if (head == null) {
            return null;
        }

        List<NTreeNode> children = new ArrayList<>();
        while (head.right != null) {
            children.add(new NTreeNode(head.val, de(head.left)));
            head = head.right;
        }
        return children;
    }


    /**
     * 主函数很简单， 就是创建一个二叉树节点，然后把ntree的所有子节点作为二叉树节点的左子树
     *
     * @param nTreeNode
     * @return
     */
    private static TreeNode n2bin(NTreeNode nTreeNode) {
        if (nTreeNode == null) {
            return null;
        }

        TreeNode treeNode = new TreeNode(nTreeNode.val);
        treeNode.left = en(nTreeNode.childrens);
        return treeNode;

    }

    /**
     * 注意 这里base case隐藏在循环中了
     *
     * @param childrens
     * @return
     */
    private static TreeNode en(List<NTreeNode> childrens) {
        TreeNode head = null;
        TreeNode cur = null;
        if (childrens!=null) {//如果为空 就是base case
            for (NTreeNode node : childrens) {
                //如果cur==null 表示是第一次循环 需要先创建第一个阶段
                if (cur == null) {
                    //注意 这里会返回一个封装好的子节点
                    cur = new TreeNode(node.val, en(node.childrens));//递归
                    head = cur;

                } else {
                    cur.right = new TreeNode(node.val, en(node.childrens));
                    cur = cur.right;
                }
            }
        }

        return head;
    }
}
